Corelab Seminar
2015-2016
Kyriakos Axiotis, Lydia Zakinthinou
Hardness in P: No strongly subquadratic algorithms for Frechet distance and Edit distance unless SETH fails
Abstract.
A central goal of theoretical computer science is the classification of computational problems according to their complexity. The theory of NP-hardness has been successful in identifying problems that are unlikely to be solvable in polynomial time. Conversely, for many problems of practical interest, the field has developed polynomial time algorithms. However, improving the running times of many of these algorithms has been a long-standing open problem, with little to no progress. Thus, being able to prove that these algorithms are indeed optimal would be a great accomplishment of the theory of algorithms.
Since unconditional lower bounds seem hard to obtain, an approach for proving hardness of problems in P is to identify plausible complexity-theoretic conjectures and show that the best algorithms for the problems of interest are optimal if one assumes these conjectures. Such popular conjectures include the (Strong) Exponential Time Hypothesis, the conjecture that all-pairs shortest paths (APSP) requires essentially cubic time, or that 3SUM requires essentially quadratic time.
We will focus on two well-known problems: Frechet distance and Edit distance computation. Assuming the Strong Exponential Time Hypothesis, it can be proved that neither of these two problems can be solved in strongly subquadratic time.
Papers
http://arxiv.org/abs/1404.1448
http://arxiv.org/abs/1412.0348